import java.util.LinkedList;
import java.util.Queue;

public class Solution1091 {
    public int shortestPathBinaryMatrix(int[][] grid) {
        if (grid[0][0]==1){
            return -1;
        }
        Queue<int[]> queue=new LinkedList<>();
        int[][] visit=new int[grid.length][grid.length];
        for (int i=0;i<visit.length;i++){
            for (int j=0;j<visit.length;j++){
                visit[i][j]=Integer.MAX_VALUE;
            }
        }
        visit[0][0]=1;
        queue.offer(new int[]{0,0});
        int[] dx=new int[]{-1,-1,-1,0,0,1,1,1};
        int[] dy=new int[]{-1,0,1,-1,1,-1,0,1};
        while (!queue.isEmpty()){
            int[] p=queue.poll();
            for (int i=0;i<8;i++){
                int x=p[0]+dx[i];
                int y=p[1]+dy[i];
                if (x>=0 && x<grid.length && y>=0 && y<grid.length && visit[x][y]>visit[p[0]][p[1]]+1 && grid[x][y]==0){
                    visit[x][y]=visit[p[0]][p[1]]+1;
                    queue.offer(new int[]{x,y});
                }
            }
        }
        if (visit[grid.length-1][grid.length-1]==Integer.MAX_VALUE){
            return -1;
        }else {
            return visit[grid.length-1][grid.length-1];
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution1091().shortestPathBinaryMatrix(new int[][]{{0,0,0},{1,1,0},{1,1,0}}));
    }
}
